#include <iostream>
typedef int ElemType;
class ThreadNode {
  public:
    ThreadNode(){};
    explicit ThreadNode(ElemType _data) : data(_data), lchild(nullptr), ltag(0), rchild(nullptr), rtag(0) {}
    ElemType data;
    ThreadNode *lchild, *rchild;
    int ltag, rtag;
};

ThreadNode* createBitTree()
{
  ThreadNode* head = new ThreadNode(12);
  head->lchild = new ThreadNode(9);
  head->rchild = new ThreadNode(13);
  //head->lchild->lchild = new ThreadNode(8);
  //head->lchild->rchild = new ThreadNode(11);
  //head->rchild->lchild = new ThreadNode(12);
  //head->rchild->rchild = new ThreadNode(20);
  return head;
}

void inOrder(ThreadNode* tree)
{
  if (tree != nullptr) {
    inOrder(tree->lchild);
    std::cout << tree->data << std::endl;
    inOrder(tree->rchild);
  }
}

void inThread(ThreadNode* p, ThreadNode** ppre)
{
  if (p != nullptr) {
    inThread(p->lchild, ppre);
    if (p->lchild == nullptr) {
      p->lchild = *ppre;
      p->ltag = 1;
    }
    if (*ppre != nullptr && (*ppre)->rchild == nullptr) {
      (*ppre)->rchild = p;
      (*ppre)->rtag = 1;
    }
    *ppre = p;
    inThread(p->rchild, ppre);
  }
}

void inThreadOrder(ThreadNode* tree)
{
  if (tree != nullptr) {
    if (tree->ltag == 0)
    inThreadOrder(tree->lchild);
    std::cout << tree->data << std::endl;
    if (tree->rtag == 0)
    inThreadOrder(tree->rchild);
  }
}

void inOrderTraverse_Thr(ThreadNode* head)
{
  ThreadNode* p = head->lchild;
  while (p != head) {
    while (p->ltag == 0) {
      p = p->lchild;
    }
    std::cout << p->data << std::endl;
    while (p->rtag == 1 && p->rchild != head) {
      p = p->rchild;
      std::cout << p->data << std::endl;
    }
    p = p->rchild;
  }
}

void inOrderThr(ThreadNode* head)
{
  ThreadNode* p = head->lchild;
  while (p != head) {
    while(p->ltag == 0) {
      p = p->lchild;
    }
    std::cout << p->data << std::endl;
    while (p->rtag == 1 && p->rchild != head) {
      p = p->rchild;
      std::cout << p->data << std::endl;
    }
    p = p->rchild;
  }

}

int main(int argc, char* argv[])
{
  ThreadNode* tree = createBitTree();
  inOrder(tree);
  std::cout << std::endl;

  ThreadNode* head = new ThreadNode();

  ThreadNode* pre = head;
  inThread(tree, &pre);
  pre->rchild = head;
  pre->rtag = 1;
  /* 建立线索二叉树后不能使用原有中序编译方式
  // inOrder(tree); */
  inThreadOrder(tree);

  head->lchild = tree;
  head->ltag = 0;
  head->rchild = pre;
  head->rtag = 1;
  //inOrderTraverse_Thr(head);
  inOrderThr(head);

  return 0;
}

